﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ChainTree
{
	class Program
	{
		static void Main(string[] args)
		{
			ChainTreeManager manager = new ChainTreeManager();
			//插入节点操作
			ChainTree<string> tree = CreateRoot();
			//插入节点数据
			AddNode(tree);

			//先序遍历
			Console.WriteLine("\n先序结果为： \n");
			manager.BinTreeDLR(tree);

			//中序遍历
			Console.WriteLine("\n中序结果为： \n");
			manager.BinTreeLDR(tree);

			//后序遍历
			Console.WriteLine("\n后序结果为： \n");
			manager.BinTreeLRD(tree);

			Console.WriteLine("\n层次结果为：\n");
			manager.Length = 100;
			manager.BinTreeLevel(tree);

			Console.WriteLine("\n树的深度为：" + manager.BinTreeLen(tree) + "\n");
			Console.ReadLine();
		}

		/// <summary>
		/// 生成根节点
		/// </summary>
		/// <returns></returns>
		static ChainTree<string> CreateRoot()
		{
			ChainTree<string> tree=new ChainTree<string>();
			Console.WriteLine("请输入根节点，方便我们生成树\n");
			tree.data = Console.ReadLine();
			Console.WriteLine("根节点已经生成\n");
			return tree;
		}

		/// <summary>
		/// 插入节点操作
		/// </summary>
		/// <param name="tree"></param>
		/// <returns></returns>
		static ChainTree<string> AddNode(ChainTree<string> tree )
		{
			ChainTreeManager manager=new ChainTreeManager();
			while (true)
			{
				ChainTree<string> node=new ChainTree<string>();
				Console.WriteLine("请输入要插入节点的数据:\n");
				node.data = Console.ReadLine();
				Console.WriteLine("请输入要查找父节点的数据:\n");
				var parentData = Console.ReadLine();
				if(tree==null)
				{
					Console.WriteLine("未找到您输入的父节点，请重新输入。");
					continue;
				}
				Console.WriteLine("请确定要插入到父节点的:1 左侧，2 右侧");
				Direction direction = (Direction)Enum.Parse(typeof(Direction), Console.ReadLine());
				tree = manager.BinTreeAddNode(tree, node, parentData, direction);
				Console.WriteLine("插入成功，是否继续？  1 继续， 2 退出");
				if(int.Parse(Console.ReadLine())==1)
					continue;
				else
					break;
			}
			return tree;
		}
	}

	#region 插入左节点或者右节点

	public enum Direction
	{
		Left=1,
		Right=2
	}

	#endregion

	#region 二叉链表存储结构

	public class ChainTree<T>
	{
		public T data;
		public ChainTree<T> left;
		public ChainTree<T> right;
	}

	#endregion

	#region 二叉树的操作帮助类

	public class ChainTreeManager
	{
		//层的length
		public int Length { get; set; }

		#region 将指定的节点插入到二叉树中

		public ChainTree<T> BinTreeAddNode<T>(ChainTree<T> tree, ChainTree<T> node, T data, Direction direction)
		{
			if (tree == null)
				return null;
			if (tree.data.Equals(data))
			{
				switch (direction)
				{
					case Direction.Left:
						if (tree.left != null)
							throw new Exception("树的左节点不为空，不能插入");
						else
							tree.left = node;
						break;
					case Direction.Right:
						if (tree.right != null)
							throw new Exception("树的右节点不为空，不能插入");
						else
							tree.right = node;
						break;
				}
			}
			BinTreeAddNode(tree.left, node, data, direction);
			BinTreeAddNode(tree.right, node, data, direction);
			return tree;
		}

		#endregion

		#region 获取二叉树指定孩子的状态

		public ChainTree<T> BinTreeChild<T>(ChainTree<T> tree, Direction direction)
		{
			ChainTree<T> childNode = null;
			if (tree == null)
				throw new Exception("二叉树为空");
			switch (direction)
			{
				case Direction.Left:
					childNode = tree.left;
					break;
				case Direction.Right:
					childNode = tree.right;
					break;
			}
			return childNode;
		}


		#endregion

		#region 获取二叉树的深度

		public int BinTreeLen<T>(ChainTree<T> tree)
		{
			int leftLength;
			int rightLength;
			if (tree == null)
				return 0;
			//递归左子树的深度
			leftLength = BinTreeLen(tree.left);
			//递归右子树的深度
			rightLength = BinTreeLen(tree.right);
			if (leftLength > rightLength)
				return leftLength + 1;
			else
				return rightLength + 1;
		}

		#endregion

		#region 判断二叉树是否为空

		public bool BinTreeIsEmpty<T>(ChainTree<T> tree)
		{
			return tree == null ? true : false;
		}

		#endregion

		#region 在二叉中查找指定的key

		public ChainTree<T> BinTreeFind<T>(ChainTree<T> tree, T data)
		{
			if (tree == null)
				return null;
			if (tree.data.Equals(data))
			{
				return tree;
			}
			return BinTreeFind(tree, data);
		}

		#endregion

		#region 清空二叉树

		public void BinTreeClear<T>(ChainTree<T> tree)
		{
			//递的结束点，归的起始点
			if (tree == null)
			{
				return;
			}
			BinTreeClear(tree.left);
			BinTreeClear(tree.right);
			//在归的过程中，释放当前节点的数据空间
			tree = null;
		}

		#endregion

		#region 二叉树的先序遍历 (DLR)

		public void BinTreeDLR<T>(ChainTree<T> tree)
		{
			if (tree == null)
				return;
			//先输出根元素
			Console.Write(tree.data + "\t");
			//然后遍历左子树
			BinTreeDLR(tree.left);
			//最后遍历右子树
			BinTreeDLR(tree.right);
		}

		#endregion

		#region 二叉树的中序遍历 (LDR)

		public void BinTreeLDR<T>(ChainTree<T> tree)
		{
			if (tree == null)
				return;
			//优先遍历左子树
			BinTreeLDR(tree.left);
			//然后输出节点
			Console.Write(tree.data + "\t");
			//最后遍历右子树
			BinTreeLDR(tree.right);
		}

		#endregion

		#region 二叉树的后序遍历 (LRD)

		public void BinTreeLRD<T>(ChainTree<T> tree)
		{
			if (tree == null)
				return;
			//优先遍历左子树
			BinTreeLRD(tree.left);
			//然后遍历右子树
			BinTreeLRD(tree.right);
			//最后输出节点
			Console.Write(tree.data + "\t");
		}

		#endregion

		#region 二叉树的按层遍历

		public void BinTreeLevel<T>(ChainTree<T> tree)
		{
			if (tree==null)
			{
				return;
			}
			ChainTree<T>[] treeList=new ChainTree<T>[Length];
			int head = 0;
			int tail = 0;
			//存放数组
			treeList[tail] = tree;
			//循环链中计算tail位置
			tail = (tail + 1)%Length;
			while (head!=tail)
			{
				var tempNode = treeList[head];
				head = (head + 1)%Length;
				//输出节点
				Console.Write(tempNode.data+"\t");
				//如果左子树不为空,则将左子树存于数组的tail位置
				if(tempNode.left!=null)
				{
					treeList[tail] = tempNode.left;
					tail = (tail + 1)%Length;
				}
				//如果右子树不为空，则将右子树存于数组的tail位置
				if (tempNode.right != null)
				{
					treeList[tail] = tempNode.right;
					tail = (tail + 1) % Length;
				}
			}


		}

		#endregion
	}

	#endregion
}
